/*
 *	Only Suport Key That is String or uint32 data type now, but that can suport other data type in coming
 *	Data: 2016-2-22
 *	Where: YOUZU
 *	Author: threadfly
 */

package hashtable

import (
	"container/list"
	"errors"
	"fmt"
	"reflect"
)

// constant
const (
	HASH_ELEMENT_NUM_THRESHOLD            = 300
	HASH_ELEMENT_NUM_THRESHOLD_DOWN_FLOAT = 50
	HASH_ELEMENT_NUM_THRESHOLD_UP_FLOAT   = 300

	HASH_ARRAY_LENGTH                 = 30
	HASH_ARRAY_LENGTH_CHANGE_MULTIPLE = 2
)

// struct
type HashElem interface {
	Key() interface{} // return value only suport string and integer
}

type HashTable struct {
	array    []*list.List
	elemNum  uint64
	elemType string
}

// function

// public
func NewHashTable() *HashTable {
	return &HashTable{
		array: make([]*list.List, HASH_ARRAY_LENGTH, HASH_ARRAY_LENGTH),
	}
}

func (this *HashTable) Len() uint64 {
	return this.elemNum
}

func (this *HashTable) Insert(elem HashElem) error {
	if err := this.checkDoExpand(); err != nil {
		return err
	}

	key := elem.Key()
	if err := this.checkKeyType(key); err != nil {
		return err
	}

	hashi, err := hash(key)
	if err != nil {
		return err
	}

	l := this.array[hashi]
	if l == nil {
		this.array[hashi] = list.New()
		l = this.array[hashi]
	}

	for e := l.Front(); e != nil; e = e.Next() {
		he := e.Value.(HashElem)
		if err := comparekey(he.Key(), key); err == nil {
			return errors.New("two key equal, key:" + fmt.Sprintf("%v", key))
		}
	}

	l.PushBack(elem)
	this.elemNum++
	return nil
}

func (this *HashTable) Delete(key interface{}) error {
	if err := this.checkDoShrink(); err != nil {
		return err
	}

	if err := this.checkKeyType(key); err != nil {
		return err
	}

	hashi, err := hash(key)
	if err != nil {
		return err
	}

	l := this.array[hashi]
	if l == nil {
		return errors.New("no have the elem that have key\n")
	}

	for e := l.Front(); e != nil; e = e.Next() {
		he := e.Value.(HashElem)
		if err := comparekey(he.Key(), key); err != nil {
			return err
		} else {
			l.Remove(e)
			this.elemNum--
			return nil
		}
	}

	return errors.New("no have the elem that have key\n")
}

func (this *HashTable) Find(key interface{}) (*HashElem, error) {
	if err := this.checkKeyType(key); err != nil {
		return nil, err
	}

	hashi, err := hash(key)
	if err != nil {
		return nil, err
	}

	l := this.array[hashi]
	if l == nil {
		return nil, errors.New("no have the elem that have key\n")
	}

	for e := l.Front(); e != nil; e = e.Next() {
		he := e.Value.(HashElem)
		if err := comparekey(he.Key(), key); err == nil {
			return e.Value.(*HashElem), nil
		} else {
			return nil, err
		}
	}

	return nil, errors.New("no have the elem that have key\n")
}

func (this *HashTable) All() []*HashElem {
	slice := make([]*HashElem, 0, this.elemNum)
	for _, l := range this.array {
		if l != nil {
			for elem := l.Front(); elem != nil; elem = elem.Next() {
				slice = append(slice, elem.Value.(*HashElem))
			}
		}
	}

	return slice
}

func (this *HashTable) Dump(out bool) string {
	var ret string
	var index uint64
	for _, l := range this.array {
		if l != nil {
			for elem := l.Front(); elem != nil; elem = elem.Next() {
				hashElem := elem.Value.(HashElem)
				hashKey, err := hash(hashElem.Key())
				if err != nil {
					fmt.Printf("%v", err)
					return ""
				}
				ret += fmt.Sprintf("%d : hashkey:%d elem:%v\n", index, hashKey, hashElem)
				index++
			}
		}
	}

	if out {
		fmt.Print(ret)
	}
	return ret
}

// private

/*
 * param: suport string and integer
 */
func hash(key interface{}) (uint32, error) {
	switch key.(type) {
	case string:
		sum := uint32(0)
		for _, b := range key.(string) {
			sum += uint32(b) << 24
		}
		return uint32(sum % HASH_ARRAY_LENGTH), nil
	case uint32:
		return uint32(key.(uint32) % HASH_ARRAY_LENGTH), nil
	default:
		keyType := reflect.ValueOf(key).String()
		return 0, errors.New("no suport key type:" + keyType + "\n")
	}
}

func comparekey(key1, key2 interface{}) error {
	key1Type := reflect.ValueOf(key1).String()
	key2Type := reflect.ValueOf(key2).String()
	if key1Type != key2Type {
		return errors.New("key type no same, key1Type:" + key1Type + " key2Type:" + key2Type + "\n")
	}
	switch key1.(type) {
	case string:
		if key1 == key2 {
			return nil
		}
	case uint32:
		if key1 == key2 {
			return nil
		}
	default:
		return errors.New("no suport key type:" + key1Type + "\n")
	}
	return errors.New("key type no equal, key1Type:" + key1Type + " key2Type:" + key2Type + "\n")
}

func (this *HashTable) checkKeyType(key interface{}) error {
	keyType := reflect.TypeOf(key).String()
	if this.elemNum == 0 {
		this.elemType = keyType
		return nil
	}

	if this.elemType != keyType {
		return errors.New("Type no same " + this.elemType + " != " + keyType + "\n")
	}

	return nil
}

func (this *HashTable) checkDoExpand() error {
	if this.elemNum > uint64(HASH_ELEMENT_NUM_THRESHOLD+HASH_ELEMENT_NUM_THRESHOLD_UP_FLOAT) {
		//TODO expand hash array
	}

	return nil
}

func (this *HashTable) checkDoShrink() error {
	if this.elemNum < uint64(HASH_ELEMENT_NUM_THRESHOLD-HASH_ELEMENT_NUM_THRESHOLD_DOWN_FLOAT) {
		//TODO expand hash array
	}
	return nil
}
